%\chapter[Réplication optimiste]{Spécifications et algorithmes pour un mécanisme de réplication optimiste sur réseau P2P}
\chapter{Spécifications et algorithmes pour un mécanisme de réplication optimiste sur réseau P2P}

Ce chapitre constitue un des livrables du sous-projet 1 : Réplication
et fusion de données.  En complément du document L2.2 livré
précédemment, il décrit l'architecture et les spécifications du
composant de réplication conçu pour XWiki.

Il est organisé de la façon suivante:
\begin{itemize}
\item la première partie est une introduction repositionnant le document
  dans le projet et les autres livrables,
\item la deuxième section est consacrée à l'architecture du composant
  et présente les sous-composants,
\item la troisième section décrit les interfaces des sous-composants,
\item enfin, la dernière partie décrit et spécifie chaque sous-composant.
\end{itemize}

Les rédacteurs de ce chapitre sont:
\begin{itemize}
\item pour l'INRIA : Pascal Molli, Mounir Tlili, Julien Maire, Gérôme Canals, Patrick Valduriez, Esther Pacitti, W. Kokou Dedzoe
\item pour XPN : Stéphane Laurière, Sergiu Dumitriu
\end{itemize}


\section{Introduction}

Ce chapitre présente une architecture et des spécifications pour un
mécanisme de réplication optimiste sur réseau P2P couplé à XWiki. Il
vient en complément du livrable L2.2~\cite{xwikiconcerto-l2}, également issu du sous-projet 1,
livré en aoűt 2007.

Ce document décrivait, dans la section L2-2.3, 2 approches retenues
pour réaliser la réplication des données dans XWiki Concerto :
\begin{itemize}
\item l'approche basée sur l'algorithme Woot (cf. L2-2.3.2.2 et
  L2-2.3.3.1),
\item l'approche basée sur So6/KTS (cf. L2-2.3.2.3 et L2-2.3.3.2)
\end{itemize}

D'autre part, les choix architecturaux (architecture SOA orientée
service) principaux, ainsi que l'architecture générale du mécanisme de
réplication ont été décrit dans L2-2.4.  De même, l'architecture et
les spécifications du composant réalisant l'approche Woot sont
présentés dans L2-2.4.1.2. L'implantation de cette architecture fait
l'objet du livrable L4 : Prototype V1, Services P2P de base et
réconciliation des données.

Le présent document décrit l'architecture et les spécifications d'un
composant de réplication basée sur l'approche dite ``So6/KTS''. Le
principe et les algorithmes associés ont été présentés dans L2.

Rappelons simplement qu'il s'agit d'un nouveau mécanisme de
réplication optimiste combinant:
\begin{itemize} 

\item un algorithme de réconciliation de données basé sur une approche
  de transformées opérationnelles\cite{molli03:group}. Ce composant
  est similaire à So6, le synchroniseur de données de la forge
  collaborative LibreSource. Il fait cependant l'objet d'une
  réécriture complète (pour des raisons de compatibilité de licence)
  et est désormais nommé SB (Antimony).

\item une extension du service KTS\cite{akbarinia2007dcr}, nommé
  P2P-LTR (Log-Timestamper-for-Reconciliation) qui intègre un
  mécanisme d'estampillage fiable et réparti fonctionnant sur un
  modèle de réseau à base de DHT pour gérer la fraîcheur des
  répliques.

\end{itemize}


Dans une première partie, nous présentons les concepts de base de
notre solution. Puis, dans une deuxième partie nous détaillons
l'architecture de notre système ainsi que le principe de l'algorithme
de réplication utilisé.

\section{Architecture}

Cette partie est consacrée à la description de l'architecture générale
conçue pour répliquer des données XWiki sur un réseau P2P, et à la
spécification des différents composants de cette architecture.

\begin{figure}
  \centering
  \includegraphics[width=\textwidth]{figures/General_archi.png}
  \caption{Architecture générale}
  \label{fig:archigen}
\end{figure}

Le système est composé de 3 composants (figure~\ref{fig:archigen}):

\begin{center}
\begin{tabular}{|p{2.5in}|p{2in}|}
  \hline
\multicolumn{2}{|l|}{\bf{Composant}}  \\
  \hline
\multicolumn{2}{|c|}{  XWiki-Patch:\emph{interface de patchs pour XWiki}}  \\
  \hline
  {\bf Responsabilités} & {\bf Collaborateurs}\\
  \hline
  \begin{itemize} 
  \item Gère le journal des opérations d'un serveur XWiki
  \item Applique des patchs sur un serveur XWiki
\end{itemize}
& 
\begin{itemize}
\item SB 
\end{itemize}
 \\
  \hline
\end{tabular}
\end{center}

 XWiki-Patch est un composant permettant d'abstraire
  les interactions entre SB et XWiki. Toute modification dans une page
  XWiki est rendue disponible sous forme d'un patch par ce
  composant. Le format de ce patch a été défini dans le livrable
  L2. Ce composant publie un service permettant à SB de venir
  régulièrement prélever les nouvelles modifications. Ce composant est
  aussi capable d'appliquer un patch. Le fonctionnement de ce
  composant est décrit dans la section~\ref{sec:xwiki-patch}.



\begin{center}
\begin{tabular}{|p{2.5in}|p{2in}|}
  \hline
\multicolumn{2}{|l|}{\bf{Composant}}  \\
  \hline
\multicolumn{2}{|c|}{  SB:\emph{Composant de fusion de patchs concurrents}}  \\
  \hline
  {\bf Responsabilités} & {\bf Collaborateurs}\\
  \hline
  \begin{itemize} 
  \item Fusion des patchs concurrents
\end{itemize}

& 
\begin{itemize}
\item XWiki-Patch
\item P2P-LTR
\end{itemize}
 \\
  \hline
\end{tabular}
\end{center}

SB est le composant permettant de fusionner deux patchs
  concurrents. Il consulte à intervalle régulier le service
  XWiki-Patch ainsi que le service P2P-LTR. 

  De manière intuitive, SB va chercher les modifications locales et
  tente de les publier. Si cette publication échoue, cela signifie
  qu'il existe un changement concurrent. Dans ce cas, il faut
  fusionner les deux changements, appliquer le changement concurrent
  localement et tenter de republier le changement local transformé sur
  la DHT.

  Pour que l'algorithme soit correct, les patchs relatifs à une page
  doivent être totalement ordonnés. Cette garantie est offerte par le
  composant LTR.

  Pour garantir la convergence des wikis, il faut que la fonction
  $(p1',p2')=merge(p1,p2)$ soit commutative et associative. Cette
  garantie est donnée par l'algorithme SOCT4~\cite{vidot2000ccd}. Son
  utilisation est décrite dans la section~\ref{sec:sb-component}.


\begin{center}
\begin{tabular}{|p{2.5in}|p{2in}|}
  \hline
\multicolumn{2}{|l|}{\bf{Composant}}  \\
  \hline
\multicolumn{2}{|c|}{  P2P-LTR:\emph{Log Timestamper for Reconciliation}}  \\
  \hline
  {\bf Responsabilités} & {\bf Collaborateurs}\\
  \hline
  \begin{itemize} 
  \item Diffuser les patchs sur la DHT en garantissant un ordre total
    continu sur les patchs d'une même page
\item Récupération d'un patch en donnant son identifiant
\end{itemize}

& 
\begin{itemize}
\item SB 
\end{itemize}
 \\

  \hline
\end{tabular}
\end{center}


Le composant P2P-LTR propose un mécanisme d'estampillage fiable, réparti et
fonctionnant sur un réseau P2P utilisant une DHT. Il sert non
seulement à estampiller les opérations reçues mais à les faire stocker
dans la DHT en garantissant l'ordre total.  En effet, Le composant SB
n'échange pas directement les patchs avec les autres applications
clientes: il doit d'abord les faire transiter par le composant
P2P-LTR. Ce dernier estampille les patchs selon un ordre total avant
de les stocker dans plusieurs n\oe{}uds dans la DHT. S'il y a des
nouveaux patchs dans la DHT, le composant SB doit d'abord récupérer
toutes les patchs estampillés manquants et ensuite il est possible de
publier ses opérations locales dans la DHT. Le fonctionnement de ce
composant est décrit dans la section~\ref{sec:p2p-ltr}.

\begin{figure}[htb]
  \centering
  \includegraphics[width=\textwidth]{figures/depl.png}
  \caption{Déploiement de SbLtr}
  \label{fig:depl}
\end{figure}

La figure~\ref{fig:depl} illustre un déploiement possible de la
solution SbLtr. Les n\oe{}uds ``chord'' représentent la DHT chord. Les
composants SB et LTR doivent raisonnablement s'exécuter sur la même
machine. Le composant XWiki-Patch et le serveur Xwiki doivent
s'exécuter sur la même machine que Xwiki. Dans notre figure, on
synchronise 2 serveurs XWiki en utilisant une DHT de 3 n\oe{}uds
chords. 1 serveur XWiki tourne sur la même machine que SB-LTR. L'autre
serveur XWiki tourne sur 1 serveur dédié. Le composant SB-LTR accède a
XWiki en utilisant des appels XML-RPC. Il est à note qu'un couple
$SB+LTR$ n'est associé qu'à 1 seul serveur XWiki.



\section{Interfaces }

\begin{figure}[htb]
  \centering
  \includegraphics[width=\textwidth]{figures/General_archi_advanced.png}
  \caption{Architecture générale détaillée}
  \label{fig:archigen2}
\end{figure}

La figure~\ref{fig:archigen2} décrit l'architecture générale en détaillant les interfaces en jeu.

La figure~\ref{fig:archigen2} décrit l'architecture détaillée de
SB-LTR. Nous détaillons dans les sections~\ref{sec:patchservice} et
\ref{sec:ltrservice} les opérations définies dans les interfaces.

\subsection{PatchService}
\label{sec:patchservice}

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.5\textwidth]{figures/PatchService_Interface.png}
  \caption{Interface PatchService}
  \label{fig:patchserviceI}
\end{figure}

L'interface~\ref{fig:patchserviceI} est appelée par le composant
Antimony régulièrement. En effet, il doit récupérer les patchs
proposés par le service de patch, mais aussi lui en fournir. Ainsi,
l'interface~\ref{fig:patchserviceI} fournit l'ensemble des méthodes
nécessaires à la gestion du flux de patchs transitant entre le
composant Antimony et le composant PatchService.


\begin{itemize}
\item La méthode $push(Serializable p)$ est utilisée pour appliquer un
  patch. C'est à l'appelant de s'assurer que le patch n'a pas déjà été
  appliqué.

\item La méthode $pull()$ est utilisée pour chercher un nouveau patch
  produit localement. Chaque appel à la méthode $pull()$ consomme le
  message. Si il existe 1 patch $p$ disponible sur 1 serveur XWiki, un
  premier appel à la méthode pull() retourne $p$, un second appel 
  retourne $null$ (cela signifie qu'il n'y a pas de nouveaux patchs
  disponibles).

\item La méthode $getOldPatch(Id)$ retourne le patch identifié par
  $id$ ou $null$ si ce patch n'existe pas.

La spécification de l'objet Patch est décrite dans la section~\ref{sec:xwiki-patch}.
\end{itemize}


\subsection{LTRService}
\label{sec:ltrservice}

La communication entre le composant SB et P2P-LTR est assurée via
l'interface décrite dans la figure~\ref{fig:ltrservice}. 

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\textwidth]{figures/LTRService_Interface.png}
  \caption{Interface LTRService}
  \label{fig:ltrservice}
\end{figure}


\begin{itemize}

\item $long lastTimestamp(String \, key)$: cette méthode retourne le
  dernier timestamp généré pour la clé $key$. La clé $key$ identifie
  une page wiki. le nombre retourné correspond au dernier ticket
  produit pour cette page. Si il y a eu 3 modifications sur la page
  ``XXXDDD'' , $lastTimeStamp("XXXDDD"$) retourne 3.


\item $Serializable retrieve(String \, key,long \, n)$: Cette méthode
  permet de récupérer le patch $n$ produit sur la page wiki $key$.

\item $long sendToPublish(String key, Serializable patch, long
  timestamp)$: cette méthode publie le patch $patch$ produit sur la
  page $key$ estampillé par $timestamp$. Si l'opération réussit alors
  la méthode renvoie $timestamp$. Si elle échoue alors la méthode
  renvoie l'estampille $last$ disponible pour la page $key$. $last$
  est strictement supérieur à $timestamp$.

\end{itemize}

\section{Implémentation des composants}

\subsection{XWiki-Patch}
\label{sec:xwiki-patch}

Le composant XWiki-Patch gère le journal des opérations XWiki. Toute modification
sur une page XWiki a pour effet de créer un patch. Le composant XWiki-Patch donne accès à ce journal et permet à une application distante d'exécuter un patch.

Un patch est un fichiers XML décrivant les opérations atomiques
effectuées sur chaque serveur XWiki. Le composant XWiki-Patch les met
à disposition par l'intermédiaire d'une API REST\cite{fielding02}. Les
patchs sont accompagnés d'une signature garantissant l'intégrité des
données lors du transfert. Le détail de ce composant, le format des
patchs est décrit dans le livrable L2 (LI2-1-III Architecture et
spécification, API XWiki pour la publication de patchs - structure
des patchs). Voici un exemple de patch pour information:

\lstset{language=XML}
\begin{lstlisting}{language=XML}
<patch id="IDXX" 
   document_id="myxwiki.mydocument.id" 
   author="author_id" 
   date="20070823446657808" 
   hash="20070823446657808-e14b9-451ae7bc1c4e822940526960e4d8a1faed2f5ed"
   signature="" >
<operation type="insert" position="xxx" > 
  <text> lorem ipsum factotum bukowski </text> 
</operation>
<operation type="delete" position="xxx"> 
</operation>
<operation type="set_property"> 
  <property name="author" 
            value="xwikiconcerto1234:xwiki:XWiki.John_Doe" />
</operation>
<operation type="set_object_property"> 
  <object type="XWiki.CalendarEvent" 
          index="2" 
          property="startDate" 
          value="2007-08-22" /> 
</operation>
<operation type="set_attachment"> 
  <attachment mime-type="" 
              size="" 
              author="" 
              name="" encoding=""> 
              myattachmentcontent 
  </attachment> 
</operation>
<operation type="set_type_property"> 
 <property name="location" type="String" /> 
</operation>
<operation type="delete_type"> 
 <type name="XWiki.CalendarEvent" /> 
</operation>
</patch>
\end{lstlisting}

\subsection{Composant SB}
\label{sec:sb-component}

Le composant SB assure l'intégration des patchs reçus à travers les deux
interfaces $PatchService$ et $P2P-LTR$. Il doit gérer les patchs
provenant de chaque interface.


\begin{figure}[htb]
  \centering
  \includegraphics[width=\textwidth]{figures/sbarchi.png}
  \caption{Architecture  détaillée du composant SB}
  \label{fig:sbarchi2}
\end{figure}

La figure~\ref{fig:sbarchi2} décrit l'architecture interne du composant
SB en détaillant les interfaces.

Concernant le composant $PatchService$, Antimony vérifie régulièrement
la présence ou non de patchs en attente de traitement. Lorsqu'un
patch est disponible au traitement, il est récupéré (ce qui le
supprime de la liste d'attente du composant $PatchService$) et
stocké dans le buffer. Une fois les transformations nécessaire effectuées, il est
envoyé au composant $P2PLTR$ et supprimé du buffer. Il existe un
buffer pour les patchs en provenance de XWiki-Patch et 1 autre pour
les patchs en provenance de P2PLTR. 

L'utilisation des buffers est nécessaire pour permettre au composant
Antimony d'avoir accès à tous les patchs en cours de traitement,
durant l'application de l'algorithme $Soct4$. De plus, les deux
buffers étant sérialisés, il est possible de récupérer les patchs en
cas de panne.

En ce qui concerne le composant $P2P-LTR$, Antimony maintient un
timestamp local, représentant le dernier patch transféré au
$PatchService$. Ce timestamp est géré grâce au composant
$ClockEngine$.

L'algorithme $Soct4$ est décrit par le pseudo-code suivant :


\begin{verbatim}
// Il faut régulièrement vérifier que des patchs sont publiés par le PatchService
while (true) {
   // le composant maintient une liste des pages wikis gérées.
   forall (pid in managed-pages) { 
      // Récupération de la liste des patchs publiés par le PatchService
      localPatches=XWikiPatch.getpatchs(pid);
      if (localPatches not empty) {
         foreach(p in localPatches) {
            // tentative de publication du patch 
            while (!LTRPublish(p)) { 
               // au moins un changement concurrent existe
               // pour chacun des patchs concurrents
               while ((concPatch = LTR.get(p.id+1)) != null) {
                  localPatches = updateAndMergeIfNecessary(localPatches, concPatch)
               }
            }
            // le patch local est publié avec succès dans P2P-LTR
            clockEngine.setValue(clockEngine.getValue()++)
         }
      } else {
	// si aucun patch publié par le PatchService, récupération des patchs distants
	updateAndMergeIfNecessary(empty, LTR.get(p.id+1))
      }
   }
}

// Fonction permettant de transformer une liste de patchs
// en fonction d'un patch concurrent
// Si la liste donnée est vide, le patch concurrent sera
// juste appliqué par le PatchService 
updateLocalsAndMergeIfNecessary(localPatches, concPatch) {
   (localPatches',concPatch') = merge(localPatches,concPatch)
   XWikiPatch.apply(concPatch')
   clockEngine.setValue(clockEngine.getValue()++)
   localPatches=localPatches'
   return localPatches
}
\end{verbatim} 

L'algorithme employé est générique. L'algorithme est entièrement écrit
sur la base d'une interface $TransformInterface$. Ce découpage logique
permet d'injecter des fonctions de transformation spécifiques aux
opérations XWiki définies dans les patchs XWiki. 

Il est donc possible d'écrire les fonctions de transformation
permettant de traiter les insertions et suppression de blocs de texte
dans les pages, mais aussi les fonctions de transformation permettant
de traiter les méta-données des pages. Si de nouvelles fonctionnalités 
sont ajoutées à XWiki, il sera possible d'ajouter les fonctions
de transformation adéquates en conséquence.

\subsection{P2P-LTR}
\label{sec:p2p-ltr}

L'implémentation actuelle de P2P-LTR utilise la table de hachage
distribuée Open Chord\cite{OpenChord}. Une table de hachage distribuée
est une structure de données qui associe une clé à une
ressource. Chaque clé de la table est le résultat d'une fonction de
hachage appliquée à un élément de la ressource, comme par exemple, son
nom. La fonction de hachage garantit que pour deux ressources
différentes, les clés générées le seront aussi. Ainsi, l'unicité de la
clé permet d'identifier et de retrouver de manière fiable la ressource
à laquelle elle est associée. Dans le cadre des DHTs, des fonctions de
hachage standard telles que SHA-1\cite{standard1995fip} ou
MD5\cite{rivest1992rmm} sont utilisées et c'est le nom de la ressource
qui est haché.  Dans ce cadre, chaque utilisateur peut récupérer la
valeur associée à une clé donnée. Ces couples (clé, valeur) sont
répertoriés par tous les n\oe{}uds du système, de telle façon que la
déconnexion d'un utilisateur n'entraîne pas de pertes importantes pour
l'ensemble du réseau. Ainsi la DHT permet de gérer un important nombre
d'utilisateurs, ainsi que l'arrivée de nouveaux n\oe{}uds ou encore le
départ de certains n\oe{}uds.

\begin{figure}[htb]
  \centering
  \includegraphics[width=\textwidth]{figures/LTR-arch.png}
  \caption{Architecture du composant P2P-LTR}
  \label{fig:arltr}
\end{figure}

La DHT Chord\cite{stoica2001csp} repose sur une topologie en anneau 
et utilise donc une notion de successeurs et de prédécesseurs dont
elle garde trace dans sa table de routage à m entrées. Donc tout
utilisateur peut contacter directement $m$ n\oe{}uds du réseau pour
transmettre ses requêtes.  Une fonction de hachage régulière génère un
identifiant pour chaque pair à partir de son adresse IP. Ensuite,
chaque pair est placé dans l'anneau de manière à ordonner les
identifiants par ordre croissant. Ainsi, chaque pair d'identifiant n
est responsable de l'intervalle de clés ]precedent(n), n].
\begin{figure}[htb]
  \centering
\includegraphics[width=\textwidth]{figures/chord.png}
  \caption{(a) Acheminement d'une requête par
parcours de l'anneau. (b) Définition des fingers d'un pair. (c)
Acheminement d'une requête en utilisant les fingers.}
\label{fig:chord}
\end{figure}

Pour un pair donné, la simple connaissance de son prédécesseur et de
son successeur n'est pas suffisante pour garantir une bonne
performance de l'anneau, notamment en termes de nombre de sauts par
requête. La figure \ref{fig:chord}.a illustre ce type de problème avec
un anneau contenant 10 pairs avec une plage d'adressage comprise dans
l'intervalle $[0, 64[$. On peut constater que le routage d'une requête
d'un pair de clé N8 à destination de la clé K54 nécessitera 8
sauts. Afin de pallier ce problème, pour un espace de clés compris
dans l'intervalle $[0, 2m[$, chaque pair n se voit doté d'une entrée
vers les pairs, appelés fingers, de clé suivant $(n + 2i-1)$ avec $1
\leq i \leq m$.  Ainsi, le nombre maximum de pairs parcourus pour
acheminer une requête s'exprime en termes de O(log(N)). La figure
\ref{fig:chord}.b présente la table de routage du pair N8 muni de
fingers et la figure \ref{fig:chord}.c montre que la même requête de
clé K54 est cette fois acheminée en 3 sauts. La table de routage d'un
pair Chord compte ainsi O(log(N)) entrées.

Au niveau de l'implémentation du Chord, il existe actuellement une
version en Java proposée par des chercheurs de l'Université de Bamberg
en Allemagne et elle porte le nom d'Open Chord\cite{OpenChord}.  Open
Chord donne la possibilité d'utiliser la table de hachage distribuée
Chord dans des applications Java en fournissant une API permettant de
stocker dans la DHT tout objet Java Serializable, i.e. dont on peut
changer le type en type connu (une chaîne de caractères constituée de
bits par exemple) pour le transfert dans le réseau, puis lui rendre
son type d'origine une fois reçu.


% Dans notre système, les pairs sont implémentés
% comme des objets Java. Chaque objet contient le code dont il a besoin
% afin d'implémenter le service P2P-LTR. La communication entre les
% n\oe{}uds est assurée via le protocole Java RMI\cite{rmi}, permettant
% donc l'invocation des méthodes sur des objets distants.  Dans la
% version actuelle de P2P-LTR, l'utilisateur est capable de manipuler le
% réseau DHT (exp. création de la DHT, ajout / suppression d'un n\oe{}ud
% du réseau, ...), insérer et retirer des données dans et depuis la DHT,
% afficher les données stockées dans chaque n\oe{}ud ainsi que les
% listes des estampilles généré pour chaque clé.

L'approche LTR consiste à stocker le journal des modifications des
pages XWiki dans la DHT. Pour chaque page wiki, il existe une séquence
d'opérations à appliquer pour obtenir la dernière version de la page
wiki. Ces opérations sont ordonnées totalement, strictement et de
manière continue. Par exemple, pour une page ``XX'', il faut stocker
la séquence de patchs 1,2,3,4. Une séquence de patchs estampillés
1,2,2,4 est incorrecte. Deux estampilles ne peuvent être égales et il
n'est pas possible de passer de l'estampille 2 à l'estampille 4. Dans
ce but, nous attribuons pour chaque page XWiki, un ensemble de
n\oe{}uds noté Post Groupe : Master-key(key), Master-key-Succ(key),
Log-Peers(key-ts) et Log-Peer-Succ.(voir Figure \ref{fig:groupe}).

\begin{figure}[htb]
  \centering
  \includegraphics[width=\textwidth]{figures/groupe.png}
  \caption{P2P-LTR Post Groupe}
  \label{fig:groupe}
\end{figure}

\begin{itemize}
\item \textbf{Master-key Peers}:  Ce sont les n\oe{}uds responsables de
  la génération des estampilles. Ces n\oe{}uds doivent disposer au
  préalable d'un ensemble de fonctions de hachages $H_{r}=\{h_{1},
  h_{2},..., h_{n}\}$, appelé \emph{replication hash functions},
  utilisées pour la réplication des patchs dans la DHT. De façon
  distribuée, les Master-key Peers permettent la gestion des
  estampilles de différentes clés et ensuite la réplication des patchs
  estampillés dans les Log-Peers. Les opérations principales de
  Master-key Peer sont :
  \begin{itemize}
  \item $gents(key)$ produit des estampilles. Ces estampilles forment
    un ordre total strict continu.
  \item $last\_ts(key)$ retourne la dernière estampille générée pour
    la clé $key$
  \item $publish(key, patch, timestamp)$ stocke les patchs estampillés
    dans la DHT.
  \end{itemize}

\item \textbf{Master-key-Succ}: Ces n\oe{}uds remplacent les Master-key
  Peer en cas de panne et tiennent la responsabilité des répliques
  pour la dernière valeur d'estampille générée $last\_ts$.

\item \textbf{Log-Peers}: Ce sont les n\oe{}uds responsables pour le
  stockage des patchs estampillés de différents documents XWiki. Une
  opération est signalée répliquée dans les $Log-Peers$ par
  l'exécution des opérations suivantes: $Put(h_{1}(key-ts),Patch),
  Put(h_{2}(key-ts),Patch), ..., Put(h_{n}(key-ts),Patch).$

\item \textbf{Log-Peers-Succ}:
Ces n\oe{}uds remplacent les Log-Peer en cas de panne.

\end{itemize}


La gestion de la réplication dans un réseau P2P supportant la
modification simultanée de différentes copies d'un même objet est un
défi, étant donné le comportement dynamique des pairs. Afin de
garantir la cohérence et l'ordre total des estampilles nos algorithmes
doivent respecter certaines hypothèses.

\begin{itemize}
\item Chaque n\oe{}ud tient un ensemble de fonctions de hachages
  utilisées pour répliquer les données XWiki dans la DHT et pour la
  récupération des estampilles.
\item Il ne peut pas y avoir plus de n pannes simultanées des
  Log-Peers de mêmes clés.
\item Deux n\oe{}uds successeurs ne peuvent pas tomber en panne en même
  temps.
\item Durant la stabilisation des Masters-key Peers, aucune estampille
  n'est délivrée.  Si un n\oe{}ud du réseau tombe en panne, son
  successeur le remplace automatiquement.
\end{itemize}

% \subsubsection{Les DHTs}


% \subsubsection{Algorithme de Réplication du Patch dans la DHT}
% Nous détaillons dans cette partie l'algorithme de réplication des patchs dans la DHT.
% Dans un premier temps, nous décrivons le principe de fonctionnement de notre algorithme. Ensuite,
% dans un deuxième temps, nous présentons les pseudos codes
% correspondants.

\subsubsection{Principe de fonctionnement}

Dans cette section, nous présentons le principe de fonctionnement de
notre algorithme de réplication. En effet, chaque site disposant d'une
copie des données partagées génère des opérations et les intègre
localement avant de les publier dans la DHT sous forme de patch. Pour
envoyer une opération, il faut d'abord avoir reçu toutes les
opérations estampillées et les intégrer localement. Il est ensuite
possible d'estampiller les opérations locales et de les envoyer. Le
principe de fonctionnement de l'algorithme
est basé sur les Master-Key Peers qui délivrent les estampilles à
chaque opération. Les opérations sont donc estampillées selon un ordre
total.  Supposant, qu'une application cliente XWiki s'exécute sur
chaque peer. Les applications clientes ne s'échangent pas directement
les opérations, elles doivent les faire transiter par les
estampilleurs Master-Key Peers qui à leur tour les font stocker
dans les Log-Peers en utilisant un ensemble de fonction de
hachage. Ces Log-Peers maintiennent, de manière persistante, les
opérations publiées par les différents sites dans l'ordre des
estampilles.


\begin{verbatim}
XWiki-Client
1. Changement dans le document XWiki
2. Notification des changements effectués dans le document  XWiki
3. Création de Patch
Patch := PatchService.CreatePatch
4. tentation de publication de patch dans la DHT
Put(key,(patch+ts))
5. Vérification d'estampille par le Master-Key Peer   
Si ts = Last-ts alors 
	Publier le Patch dans la DHT ;
 	Envoyer un Act au XWiki-Client ;
Sinon
	Master-key Peer : retourner la dernière estampille (Last-ts);
XWiki-Client:
- Récupérer les opérations manquantes dans la DHT.
- Transformer et intégrer ses opérations locales en utilisant SB
 et ensuite les envoyer.
\end{verbatim}

\begin{verbatim}
Master-key-Peer
/** Le Master Peer est en écoute */
Si Put(key,(patch+ts)) est reçu
Si ts = last-ts
        last-ts = last-ts + 1 ;
   Envoyer notification au Post-group(key+ last-ts);
   Exécuter en paralléle A et B
A: 
put(key+ts,patch) dans les Log-Peers en utilisant l'ensemble de
functions de hachages: h_{1}...h_{n}
           B:
  	/** réplication d'estampille dans le Master-key-succ*/
put(Master-key-succ, key + last-ts)
envoyer ack + last-ts  à XWiki-Client
Sinon 
Envoyer au XWiki-Client last-ts afin de récupérer les opérations manquantes 
dans la DHT
\end{verbatim}


\section{Conclusion} 
Dans ce document, nous avons présenté l'approche SB/P2P-LTR comme
solution de réplication optimiste qui consiste à répliquer les données
d'un document XWiki dans un réseau P2P à base de DHT. Pour ordonner
les opérations publiées par les utilisateurs de système, P2P-LTR
utilise un mécanisme d'estampillage fiable qui permet de garantir
l'ordre total des estampilles.

